package com.base.dynamicprograming;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 91. 解码方法
 * 题目描述见：https://leetcode-cn.com/problems/decode-ways/
 *
 * @author leon
 * @date 2021年09月27日 18:34
 */
public class NumDecodings1 {
    /**
     * 思路：0元素由于它不能独自存在，所以必须与前面的元素一起组合成一个数。所以我们先要将0元素与前面的元素组合起来。
     * 1、第i个元素可以独立解码
     * 2、第i个元素可以与第i-1元素组合起来解码
     * @param s
     * @return
     */
    public int numDecodings(String s) {
        if (s.charAt(0) == '0') {
            return 0;
        }
        LinkedList<Integer> stack = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            int tmp = s.charAt(i) - '0';
            if (tmp == 0) {
                int top = stack.pop() * 10;
                if (top > 26) {
                    return 0;
                }
                stack.push(top);
            } else {
                stack.push(tmp);
            }
        }
        int[] toArray = new int[stack.size()];
        for (int i = toArray.length -1; i >= 0; i--) {
            toArray[i] = stack.pop();
        }
        int[] dp = new int[toArray.length];
        dp[0] = 1;
        if (toArray.length==1){
            return 1;
        }
        if (toArray[1]<10) {

            if (toArray[0] * 10 + toArray[1] <= 26) {
                dp[1] = 1 + dp[0];
            } else {
                dp[1] = dp[0];
            }
        }else {
            dp[1] = dp[0];
        }


        for(int i = 2; i < toArray.length; i++) {
            if (toArray[i]<10) {

                if (toArray[i - 1] * 10 + toArray[i] <= 26) {
                    dp[i] = dp[i - 2] + dp[i - 1];
                } else {
                    dp[i] = dp[i - 1];
                }
            }else {
                dp[i] = dp[i-1];
            }
        }

        return dp[dp.length-1];

    }

    //    作者：LeetCode-Solution
    //    链接：https://leetcode-cn.com/problems/decode-ways/solution/jie-ma-fang-fa-by-leetcode-solution-p8np/
    //    来源：力扣（LeetCode）
    //    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
    public int numDecodings1(String s) {
        int n = s.length();
        int[] f = new int[n + 1];
        // f(0)代表空字符串时，组合为1
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            if (s.charAt(i - 1) != '0') {
                f[i] += f[i - 1];
            }
            if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {
                f[i] += f[i - 2];
            }
        }
        return f[n];
    }

    public int numDecodings2(String s) {
        int n = s.length();
        // a = f[i-2], b = f[i-1], c=f[i]
        int a = 0, b = 1, c = 0;
        for (int i = 1; i <= n; ++i) {
            c = 0;
            if (s.charAt(i - 1) != '0') {
                c += b;
            }
            if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {
                c += a;
            }
            a = b;
            b = c;
        }
        return c;
    }


//    作者：LeetCode-Solution
//    链接：https://leetcode-cn.com/problems/decode-ways/solution/jie-ma-fang-fa-by-leetcode-solution-p8np/
//    来源：力扣（LeetCode）
//    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
}
